/**
 * Created by yuchen on 16/5/10.
 */
public class unionfind {
    private int[] id;
    private int count;
    private int[] sz;

    public unionfind(int n) {
        this.id = new int[n];
        this.count = n;
        this.sz = new int[n];
    }

    public int find(int p) {
        while (p != this.id[p]) {
            this.id[p] = this.id[this.id[p]];
            p = this.id[p];
        }
        return p;
    }

    public void union(int p,int q){
        int i = this.find(p);
        int j = this.find(q);
        if (i == j) {
            return;
        }
        if (this.sz[i] < this.sz[j]) {
            this.id[i] = j;
            this.sz[j] += this.sz[i];
        } else {
            this.id[j] = i;
            this.sz[i] += this.sz[j];
        }
        this.count--;
    }
}